When a central station that controls a fleet of vehicles, such as police cars, taxicabs or ambulances, receives a call for assistance, one question of immediate concern is which vehicle can respond most quickly to the call. A 911 or taxicab dispatcher will normally question the caller and determine the type of assistance needed and the location of the caller, using a Geographic Information System (GIS) or similar database to identify the caller's location on a grid or other coordinate system. The dispatcher must now determine which vehicle or vehicles is in the best position to respond to the call, based upon vehicle availability, vehicle proximity to the caller's location, special equipment and/or personnel training needed for response to this call, and possibly other factors. Vehicle availability and proximity to the caller's location require current information on each of the fleet vehicles.
If the number of vehicles in the fleet is small (e.g., five) and not too widely dispersed, it may be feasible to contact each vehicle by radiowave and learn the vehicle's present location and availability every 15-30 seconds. However, if the fleet is a large one (e.g., with 200 or more vehicles), this frequent interrogation/response mode cannot be implemented using a single channel or a reasonably small number of channels. For example, the New York City Police Department has a fleet of about 4600 vehicles, and about 5 police vehicles per second can report their present location and availability or status. If 16 channels are dedicated for such reporting, assuming 5 reports per second in a round-robin system, each vehicle can report at most once in a time interval of length 58 seconds. Further, some police vehicles that are currently in the "pursuit or deployment" mode should report their present location and status more often, perhaps once every ten seconds, and a round-robin system that assigns uniform priorities to each vehicle is not appropriate here. Further, some vehicles may not be on patrol nor operational at any given time, and interrogation of the present availability and/or location of such vehicles (which will not respond) is a waste of air time.
Local area networks (LANs) whose stations communicate by cable signals or by radio waves often face a problem of collision of two or more signals sent by one station to another station, where the content of both signals may be lost. In one of the original LANs, the ALOHA network connecting five of the Hawaiian islands, the signal collisions were severe enough that the ALOHA system experimented with an allocation of specific time slots for each station, which was of some help in the small ALOHA system. This is discussed in some detail by Mischa Schwartz in Computer-Communication Network Design and Analysis, Prentice Hall, 1977, pp. 288-320. A fixed allocation of time slots is wasteful if many of the responding stations are not operative at a given time.
Another popular approach for LANs is CSMA/CD, or carrier sense, multiple access with collision detection, in which any station may contend for "possession" of the air waves for a selected maximum time. Signal collisions are partly avoided by having each station listen to sense the presence of one or more carriers (indicating that a message is presently being transmitted by another station) before transmitting. Collisions are still a problem here, and another collision reduction algorithm is often imposed on the stations. One popular algorithm, known as random backoff, requires two stations whose signals have collided (and any other station that senses the presence of this signal collision) to "back off" or refrain from further transmissions for a randomly determined time drawn from a time interval of selected maximum length, such as 16 seconds. Schwartz, ibid, shows that, without time slot allocation, a system will theoretically saturate, so that signal collisions allow substantially no transmissions, as soon as at least 19 percent of the stations are attempting to transmit. If time slot allocation is implemented, the threshold at which saturation will occur improves to about 37 percent. These results indicate that saturation can be continually present where a large fleet of vehicles communicates with a central station, even with modest throughput requirements, unless the communication protocol is carefully selected and implemented.
Where system saturation is a concern, some workers have assigned general time slots for use in exchanging information between stations. Fujiwara, in U.S. Pat. No. 4,513,416, discloses a TDMA satellite-communication system with a ground station that counts the number of idle time slots in each uplink or downlink signal. When this idle number exceeds a selected number, one of the idle time slots in an uplink and in a down link signal is assigned to time axis adjustment and is no longer available for its original use. However, at any time some of the time slots may be idle and unused.
A radio communication system that adapts itself to the amount of signal traffic is disclosed in U.S. Pat. No. 5,103,445, issued to Ostlund. A receiving station determines whether a given time slot allocated for transmission is likely to be filled or empty, based on the signal traffic sensed by the station in a time slot used for an earlier invitation-to-transmit message. This patent disinguishes between three types of time slots (containing an understandable message, empty, and mutilated) as they appear in the system.
In U.S. Pat. No. 5,168,271, Hoff discloses a packet-based paging and timekeeping system in which time slot identification is used to transfer packets from a station on one network to a receiver on a second network. A sequence of time slots is allocated, and a packet is transmitted during a selected time slot that corresponds to and identifies the addressee network.
Yamao, in U.S. Pat. No. 5,203,024, discloses an antenna selection system that selects a particular antenna for signal reception in a specified time slot, based upon comparison of a predicted signal quality parameter for each of the antennas. The parameter may be present error rate, receive level at the center of the assigned slot, minimum receive level required, or some other parameter.
Another antenna selection system is disclosed in U.S. Pat. No. 5,203,026, issued to Ekelund. Antenna selection for the present time slot is based upon comparison of the signal quality in the immediately preceding time slot for each of a plurality of antennas.
In U.S. Pat. No. 5,126,733, Sagers et al disclose a polling system for a plurality of location determination units, here Loran signal receivers. A polling station can transmit an interrogation signal, requesting location information from all receiving stations. Alternatively, a polling station can request location information from a specified station.
Other workers have used a known signal transmission backoff algorithm in the presence of signal collisions, to reduce the likelihood of subsequent signal collisions. Hochsprung et al disclose a local area network with carrier sense collision avoidance, using a signal backoff, in U.S. Pat. No. 4,661,902. If a first station, wishing to transmit, senses the presence of a carrier or other indicia of a second station's signal, the first station executes a signal backoff for a time R .DELTA.t, where .DELTA.t is a selected number (100 .mu.sec) and R is a positive integer that is randomly chosen based upon recent network experience with signal collisions.
In U.S. Pat. No. 5,018,138, Twitty et al disclose a signal backoff algorithm for a network of communicating stations. A first station, wishing to transmit, that senses the presence of a signal already transmitted by a second station, waits for a backoff period of length specified by the I.E.E.E. 802.3 truncated binary exponential backoff standard. The backoff time is a selected time .DELTA.t multiplied by a random integer R that is uniformly distributed over an integer interval defined by 0&lt;R&lt;exp[min(I0, n)], where n is a statistically determined number of signal collisions in a selected time interval for the network, based upon recent experience and I0 is a selected integer.
The I.E.E.E. 802.3 truncated binary exponential backoff standard is also adopted for signals in response to collision detection in U.S. Pat. No. 5,164,942, issued to Kamelman et al. None of these patents uses a deterministic, as opposed to statistically determined, backoff time based upon some physically measurable quantity that is distinct for each station.
Some of these systems use signal analysis in a given time slot to determine whether a signal should be transmitted, or received, during that time slot or a subsequent time slot but do not provide an approach that reduces the required number of time slots to a minimum. Other systems use well known transmission backoff algorithms that do not take account of the special needs of a fast response system for a fleet of vehicles that continuously communicates with a central station.
What is needed is a system for communication between a central station and each vehicle in a fleet that: (1) allows the central station to poll the present status and location and other necessary information for each vehicle with a frequency that need not be uniform for all vehicles in the fleet; (2) allows the central station to advise each fleet vehicle of the location and other necessary information for each call for assistance received by the central station; (3) allows each fleet vehicle to determine its present distance from the location of a call for assistance and to advise the central station if that vehicle is within a selected distance of the caller; (4) allows each fleet vehicle to communicate with the central station, using a protocol that minimizes the likelihood of signal collision; (5) allows the central station to adjust the criteria to be used, including but not limited to a vehicle's proximity to the caller's location, in determining which vehicle(s) will respond to a call for assistance; and (6) performs these tasks with a minimum of radio channels and does not saturate as 100 percent utilization is approached.